package Example_practice02;

import java.util.Arrays;

public class HamiltonCycle {
    private  int V;//图中结点数量
    private int[] path;//存储路径
    private int[][] graph;//图的邻接矩阵
    //初始化图
    public HamiltonCycle(int[][] graph){
        this.graph=graph;
        this.V=graph.length;
        this.path=new int[V];
        Arrays.fill(path,-1);
    }
    //穷举，递归遍历所有可能的结点顺序
    public void hamiltonian(int[] path,int pos){
        //如果路径遍历完（pos==V）
        if (pos==V){
            //检查是否存在从最后一个结点到第一个结点的边
            if (graph[pos-1][0]==1){
                printPath(path);
            }
            return;
        }
        for (int v=1;v<V;v++){
            //判断当前结点是否可以添加到路径中
            if (isValid(v,path,pos)){
                path[pos]=v;
                hamiltonian(path,pos+1);
                path[pos]=-1;//回溯
            }
        }
    }
    //判断当前结点是否可以加入到路径中
    public boolean isValid(int v,int[] path,int pos){
        if (graph[path[pos-1]][v]==0){
            return false;
        }
        for (int i=0;i<pos;i++){
            if (path[i]==v){
                return false;
            }
        }
        return true;
    }
    //打印路径
    public void printPath(int[] path){
        for (int vertex: path){
            System.out.print(vertex+"->");
        }
        System.out.println(path[0]);
    }
    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 0, 1, 0},
                {1, 0, 1, 1, 1},
                {0, 1, 0, 0, 1},
                {1, 1, 0, 0, 1},
                {0, 1, 1, 1, 0}
        };
        HamiltonCycle hc = new HamiltonCycle(graph);
        hc.path[0] = 0; // 从节点0开始搜索
        hc.hamiltonian(hc.path, 1);
        //System.out.println("nnnn");
    }
}
